1. Field of the Invention
The present invention relates to a channel routing method in the layout design of a VLSI or the like.
2. Description of the Prior Art
Conventional channel routing methods include (1) methods which minimize the number of tracks and (2) methods which minimize the channel height.
Typically, the methods (1) include a grid based channel routing algorithm. For example, such methods are disclosed in "Wire routing by optimizing channel assignment" (Proc. 8th Design Automation Workshop, 1971, pp. 155-169), "A dogleg channel router" (Proc. 13th Design Automation Conf., 1976, pp. 425-433), "Efficient algorithms for channel routing" (IEEE Trans. Computer-Aided Design, vol, CAD-1, pp. 25-35, 1982), "A greedy channel router" (Proc. 19th Design Automation Conf., 1982, pp. 418-424), "Hierarchical channel router" (Proc. 20th Design Automation Conf., 1983, pp. 591-597), and "A new gridless channel router: YACR2" (Proc. of the IEEE International Conference on Computer-Aided Design, ICCAD-84, 1984, pp. 72-75). In the these methods, wiring is carried out without considering the wire width, namely, assuming that the wire widths are all the same. Since no consideration is given to design rules (except for the YACR2 method), the wire spacing is left sufficient to satisfy them even though contacts are located side by side. Therefore, minimization in channel height leads to minimization in the number of tracks.
"A variable width gridless channel router" (Proc. of International Conference on Computer-Aided Design, 1985, pp. 304-306) describes a typically known one of the methods (2). In this method, since both the wire width and the design rules are taken into consideration, the wire spacing obtained thereby is regarded as the minimum spacing in the design rules. As such, this method provides a solution which is more favorable than the methods (1) in channel height.
According to the methods (1), since channel routing is performed on the condition that the wire width is constant, the methods (1) cannot provide the optimum channel height when a plurality of wire widths exist. Further, an excessive space is formed because no consideration is given to the wire spacing, as described previously.
The above-described problem inherent in the methods (1) does not occur in the methods (2). The XY technique is used in the methods (2). According to the XY technique in two-layer channel routing, horizontal segments are placed on the first layer (second layer) whereas vertical segments are placed on the second layer (first layer). Accordingly, the horizontal segments and the vertical segments are never placed on the same layer. As a result, this method cannot provide high density channel routing by effectively making use of the two layers.